﻿// https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
// 105. 从前序与中序遍历序列构造二叉树

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <limits.h>

using namespace std;

// struct ListNode {
//     int val;
//     ListNode *next;
//     ListNode() : val(0), next(nullptr) {}
//     ListNode(int x) : val(x), next(nullptr) {}
//     ListNode(int x, ListNode *next) : val(x), next(next) {}
// };

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() == 0 || inorder.size() == 0) return nullptr;
        return Recursion(preorder, 0, preorder.size(), inorder, 0, inorder.size());
    }

private:
    TreeNode* Recursion(vector<int>& preorder, int preorder_begin, int preorder_end,
                        vector<int>& inorder, int inorder_begin, int inorder_end) {
        if (preorder_begin == preorder_end) return nullptr;

        int root_val = preorder[preorder_begin];
        TreeNode *root = new TreeNode(root_val);

        if (preorder_end - preorder_begin == 1) return root;

        int mid_index;
        for (mid_index = inorder_begin; mid_index < inorder_end; mid_index++) {
            if (inorder[mid_index] == root_val) break;
        }

        int left_inorder_begin = inorder_begin;
        int left_inorder_end = mid_index;

        int right_inorder_begin = mid_index + 1;
        int right_inorder_end = inorder_end;

        int left_preorder_begin = preorder_begin + 1;
        int left_preorder_end = preorder_begin + 1 + mid_index - inorder_begin;

        int right_preorder_begin = preorder_begin + 1 + (mid_index - inorder_begin);
        int right_preorder_end = preorder_end;

        root->left = Recursion(preorder, left_preorder_begin, left_preorder_end, 
                                inorder, left_inorder_begin, left_inorder_end);
        root->right = Recursion(preorder, right_preorder_begin, right_preorder_end, 
                                inorder, right_inorder_begin, right_inorder_end);

        return root;
    }
};

int main() {
    Solution obj = Solution();
}